package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DaiBi;
import cn.pugle.oj.catalog.DynamicProblem;

/**
 * Created by tzp on 15-10-20. <br>
 * 原理：每个字符（组）只需要和他 <u>前一个Q</u> 以及<u>前一个的前一个QQ</u> 判断是否想等，如果相等，<s>三者</s>合为一个组，循环判断直到不能合并。遍历一遍最终得到最长回文组  <br>
 * 链表<数组>的方法aaaabcbaaaa => {[aaa],[a],[bcb]}.add('a') - > {[aaa],[abcba]}  伪的树<br>
 * 但是为了节省来回 '增加删除合并数组' 的操作，使用栅栏(指针、索引)，两个栅栏之间的部分即是子数组，称为格子。栅栏的值是栅栏右边位置的index。 <br>
 * 使用栅栏也需要一个栅栏数组，对其进行的操作有，顺序存入，找到前一个的前一个，删除倒数第2，3个，so使用栅栏确实避免了对数组链表的操作，但是这些操作仍然要做 <br>
 * 使用数组,好处是只会删除最后两个，删除时需要移动的较少。再用一个指针指向last。
 * <p>
 * bugfix, 长度为2的回文没有处理..不只是长度为2 ，x aba aba x这样的。所以整个原理偏差了，不只是判断前一个的前一个，还有前一个 <br>
 * bugfix, aba mmm bb mm ,再反序列玩一次 <br>
 * bugnotfix，｛［aba aba］ aba｝｛［aba aba aba］ aba｝ 比较aba和Q的左半支：不行，｛［aba mmm aba］ aba｝比较aba和Q的前3个：不行。原理整个有问题，<b><u>判断能否合并，不是简单的看QQ和Q就行的？</u></b> <br>
 * question,｛[aba][a[b]a][aba]｝.add([aba]) 换成2x树也会有问题？ <br>
 * <p>
 * xxx 下次开写之前先想测试用例如何？？
 */
public class LC5_LongestPalindromicSubstringV3 implements DaiBi, DynamicProblem {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s.substring(0, 1);
        }
        int[] fences = new int[1000];
        fences[0] = 0;
        int lastInFences = 0;//fences中最后一个有值的位置
        int maxLength = 1, maxLengthFenceEnd = 0;
        for (int i = 0; i < s.length(); i++) {
            //放入栅栏
            lastInFences++;
            fences[lastInFences] = i + 1;
            //rebuild过程：比较这个格子和前一个的前一个，相等时合并格子（删除fence）并判断是否大于已知最大长度.直到fence少于3个或equalQ,QQ为false;
            while (lastInFences + 1 >= 3) { //当fences数量大于等于3（即格子大于2个）时
                //与QQ比较、合并 //bugfix,应该先尝试QQ合并再Q合并： ccc//先QQ合并也不行的。。｛［aba aba］ aba｝｛［aba mmm aba］ aba｝//问题在与Q合并的时候，判断能否合并是不同策略的
                boolean equalQQ = true;
                if (lastInFences + 1 >= 4) {
                    int beginQQ = fences[lastInFences - 3], endQQ = fences[lastInFences - 2], beginT1 = fences[lastInFences - 1], endT1 = fences[lastInFences];//格子，包括begin，不包括end
                    if (endQQ - beginQQ != endT1 - beginT1) {
                        equalQQ = false;
                    } else {
                        for (int x = 0; x < endQQ - beginQQ; x++) {
                            if (s.charAt(beginQQ + x) != s.charAt(beginT1 + x)) {//xxx  比错了 对称比
                                equalQQ = false;
                                break;
                            }
                        }
                    }
                    if (equalQQ) {
                        fences[lastInFences - 2] = fences[lastInFences];
                        lastInFences = lastInFences - 2;
                        if (fences[lastInFences] - fences[lastInFences - 1] > maxLength) {
                            maxLength = fences[lastInFences] - fences[lastInFences - 1];
                            maxLengthFenceEnd = lastInFences;
                        }
                    }
                } else {
                    equalQQ = false;
                }
                //与Q比较、合并
                boolean equalQ = true;
                if (lastInFences + 1 >= 3) {//bugfix 有可能因为QQ合并，这里长度就不够了
                    int beginQ = fences[lastInFences - 2], endQ = fences[lastInFences - 1], beginT2 = fences[lastInFences - 1], endT2 = fences[lastInFences];
                    if (endQ - beginQ != endT2 - beginT2) {
                        equalQ = false;
                    } else {
                        for (int x = 0; x < endQ - beginQ; x++) {
                            if (s.charAt(beginQ + x) != s.charAt(beginT2 + x)) {//xxx 比错了 对称比
                                equalQ = false;
                                break;
                            }
                        }
                    }
                    if (equalQ) {
                        fences[lastInFences - 1] = fences[lastInFences];
                        lastInFences = lastInFences - 1;
                        if (fences[lastInFences] - fences[lastInFences - 1] > maxLength) {
                            maxLength = fences[lastInFences] - fences[lastInFences - 1];
                            maxLengthFenceEnd = lastInFences;
                        }
                    }
                }
                if (!equalQ && !equalQQ) {
                    break;
                }
            }
        }
        return s.substring(fences[maxLengthFenceEnd - 1], fences[maxLengthFenceEnd]);
    }

    /*public static final class LinkList {
        char[] data;
        LinkList next = null;
        LinkList prev = null;

        public LinkList(char[] data) {
            this.data = data;
        }
    }*/

    public static void main(String[] args) {
//        System.out.println("1".substring(0, 1));
//        System.out.println(new LongestPalindromicSubstringV3().longestPalindrome("aaaabcbaaaa"));
        System.out.println(new LC5_LongestPalindromicSubstringV3().longestPalindrome("xabaabax"));
        System.out.println(new LC5_LongestPalindromicSubstringV3().longestPalindrome("ccc"));
        long beginTime = System.currentTimeMillis();
        System.out.println(new LC5_LongestPalindromicSubstringV3().longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
        System.out.println(System.currentTimeMillis() - beginTime);
    }
}
